package 数组和链表.linklist;

import 抽象数据类型.Node;

public class LinkListsort {

    //头节点
    private Node first;

    public LinkListsort() {
        first = null;
    }

    //插入一个节点，在头节点进行插入操作
    public void insertFirst(int value) {
        Node node = new Node(value);
        node.next = first;
        first = node;
    }

    //在单链表末尾添加元素
    public void insert(int value) {
        Node node = new Node(value);
        Node tmp = first;
        if (first == null) {
            first = node;
        } else {
            while (tmp.next != null) {
                tmp = tmp.next;

            }

            tmp.next = node;
        }
    }

    //显示方法
    public void display() {
        Node current = first;
        while (current != null) {
            current.display();
            current = current.next;
        }
        System.out.println();
    }

    public void sort() {

        Node pre = first;
        Node p = first.next;
        while (p != null) {
            System.out.println(p.data);
            Node curr = first;//比较节点，每次都是从头节点开始
            Node q = p.next;

            if (p.data.compareTo(first.data) < 0)//每次都是从头节点比较，如果比较的元素比头节点小，将元素插入到头节点处
            {
                pre.next = q;
                p.next = first;
                first = p;
            } else {
                while (curr.next != p) {
                    if (p.data.compareTo(curr.next.data) < 0)//将p与curr.next进行比较，方便节点插入
                    {
                        pre.next = q;
                        p.next = curr.next;
                        curr.next = p;
                        p = pre;//保证pre每次指向的的都是p前面一个节点
                    } else {
                        curr = curr.next;
                    }

                }
                pre = p;
                p = q;

            }
        }

    }

}
